4732. Иччанобиф

 

Числа Фибоначчи – это последовательность чисел F(n), которая задаётся формулой:

F(0) = 1, F(1) = 1, F(n) = F(n – 1) + F(n – 2)

По заданному числу Фибоначчи f найти его номер n. То есть следует найти такое n, что F(n) = f.

 

Вход. Число Фибоначчи f (2 ≤ f ≤ 2·109).

 

Выход. Вывести номер заданного числа Фибоначчи.

 

Пример входа

Пример выхода

3

3

 

 

РЕШЕНИЕ

числа Фибоначчи

 

Анализ алгоритма

Вычислим все числа Фибоначчи в массиве fib, положив fib[i] = F(i). Затем найдем  в этом массиве требуемое число Фибоначчи и выведем его номер.

 

Реализация алгоритма

Числа Фибоначчи вычислим в массиве fib: fib[i] = F(i).

 

#define MAX 46

int fib[MAX];

 

Заполняем массив согласно рекуррентной формуле.

 

fib[0] = 1; fib[1] = 1;

for(int i = 2; i < MAX; i++)

  fib[i] = fib[i-1] + fib[i-2];

 

Читаем входное число Фибоначчи. Ищем его в массиве fib и выводим его номер.

 

scanf("%d",&n);

for(i = 0; i < MAX; i++)

  if (fib[i] == n) printf("%d\n",i);

 

Java реализация

 

import java.util.*;

 

public class Main

{

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int n = con.nextInt();

 

    int fib[] = new int[46];   

    fib[0] = 1; fib[1] = 1;

    for(int i = 2; i < 46; i++)

      fib[i] = fib[i-1] + fib[i-2];

   

    for(int i = 0; i < 46; i++)

      if (fib[i] == n) System.out.println(i);

    con.close();

  }

}